%======================================================================
%----------------------------------------------------------------------
%               XX                           X
%                                            X
%               XX    XXX   XXX   XXX   XXX  X  XXXX
%                X   X   X X   X X   X X   X X X
%                X   XXXXX XXXXX XXXXX X     X  XXX
%                X   X     X     X     X   X X     X
%               XXX   XXX   XXX   XXX   XXX  X XXXX
%----------------------------------------------------------------------
%               SPECIFICATION FOR COMMON IEEE STYLES
%----------------------------------------------------------------------
%               Gregory L. Plett, Istv\'{a}n Koll\'{a}r.
%======================================================================
\documentclass[%
    %draft,
    %submission,
    %compressed,
    a4paper,
    %12pt,
    10pt,
    final,
    %technote,
    %internal,
    %submitted,
    %inpress,
    %reprint,
    %titlepage,
    notitlepage,
    %anonymous,
    narroweqnarray,
    inline,
    oneside,
    %invited,
    %conference
    article
    ]{ieee}

%\documentclass[a4paper,12pt]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{epstopdf}

\newcommand{\latexiie}{\LaTeX2{\Large$_\varepsilon$}}

%\usepackage{ieeetsp}    % if you want the "trans. sig. pro." style
%\usepackage{ieeetc}    % if you want the "trans. comp." style
%\usepackage{ieeeimtc}    % if you want the IMTC conference style

% Use the `endfloat' package to move figures and tables to the end
% of the paper. Useful for `submission' mode.
%\usepackage {endfloat}

% Use the `times' package to use Helvetica and Times-Roman fonts
% instead of the standard Computer Modern fonts. Useful for the
% IEEE Computer Society transactions.
%\usepackage{times}
% (Note: If you have the commercial package `mathtime,' (from
% y&y (http://www.yandy.com), it is much better, but the `times'
% package works too). So, if you have it...
%\usepackage {mathtime}

% for any plug-in code... insert it here. For example, the CDC style...
%\usepackage{ieeecdc}

\begin{document}

%----------------------------------------------------------------------
% Title Information, Abstract and Keywords
%----------------------------------------------------------------------
\title[]{
  Trabajo Pr\'actico Especial 4: Algoritmos gen\'eticos}

% format author this way for journal articles.
% MAKE SURE THERE ARE NO SPACES BEFORE A \member OR \authorinfo
% COMMAND (this also means `don't break the line before these
% commands).
%\author[PLETT AND KOLL\'{A}R]{Gregory L. Plett\member{Student
%       Member},\authorinfo{G.\,L.\,Plett is with the Department of Electrical
%       Engineering, Stanford University, Stanford, CA 94305--9510.
%       Phone: $+$1\,650\,723--4769, e-mail: glp@simoon.stanford.edu}%
%\and{}and Istv\'{a}n Koll\'{a}r\member{Fellow}\authorinfo{I.\
%       Koll\'{a}r is with the Department of Measurement and Information
%       Systems, Technical University of Budapest, 1521 Budapest, Hungary.
%       Phone: $+$\,36\,1\,463--1774, fax: +\,36\,1\,463--4112,
%       e-mail: kollar@mmt.bme.hu}
%}
\author{
     Alan Idesis,
\and Mar\'ia Eugenia Cura,
\and Tom\'as Alvarez
}

% format author this way for conference proceedings
%\author[PLETT AND KOLL\'{A}R]{%
        %Gregory L. Plett\member{Student Member},\authorinfo{%
        %Department of Electrical Engineering,\\
        %Stanford University, Stanford, CA 94305-9510.\\
        %Phone: $+$1\,650\,723-4769, email: glp@simoon.stanford.edu}%
%\and{}and%
%\and{}Istv\'{a}n Koll\'{a}r\member{Fellow}\authorinfo{%
        %Department of Measurement and Instrument Engineering,\\
        %Technical University of Budapest, 1521 Budapest, Hungary.\\
        %Phone: $+$\,36\,1\,463-1774, fax: +\,36\,1\,463-4112,
        %email: kollar@mmt.bme.hu}
%}

%\journal{IEEE Trans.\ on Instrum.\ Meas.}
%\titletext{, VOL.\ 46, NO.\ 6, DECEMBER\ 1997}
%\ieeecopyright{0018--9456/97\$10.00 \copyright\ 1997 IEEE}
%\lognumber{xxxxxxx}
%\pubitemident{S 0018--9456(97)09426--6}
%\loginfo{Manuscript received September 27, 1997.}
%\firstpage{1217}

%\confplacedate{Ottawa, Canada, May 19--21, 1997}   

\maketitle

%\begin{keywords}
%Style file, \latexiie, Microsoft Word, IEEE Publications, Instrumentation
%and Measurement Technology Conference, IMTC.
%\end{keywords}

%----------------------------------------------------------------------
% SECTION I: Introduction
%----------------------------------------------------------------------
\section*{Introducci\'on}

\PARstart El objetivo de este trabajo pr\'actico es utilizar un motor de algoritmos gen\'eticos con el objetivo 
de obtener los pesos \'optimos de la red neuronal multicapa implementada en el Trabajo Pr\'actico 2.

Se llamar\'a \textit{Funci\'on de Aptitud} o \textit{Fitness} a la funci\'on que se utiliza para obtener
como m\'etrica que tan apto es un individuo de la poblaci\'on. Dicha funci\'on es la inversa al error cuadr\'atico medio 
de la salida de la red neuronal.

La implementaci\'on del motor se realiz\'o en \textit{Matlab} al igual que la red neuronal multicapa.

En la secci\'on II se trata el desarrollo del trabajo. Se explica la aplicaci\'on de los procesos 
de selecci\'on, reproducci\'on y reemplazo por los que esta compuesto el algoritmo gen\'etico 
utilizado y las consideraciones que se tuvieron en cuenta para realizar el trabajo.

En la secci\'on III se muestran los resultados obtenidos con los distintos m\'etodos y configuraciones, 
a partir de ellos se sacan las correspondientes conclusiones.

En la secci\'on IV se presentan algunos comentarios finales.


\section*{Desarrollo}

En esta secci\'on se trata el desarrollo del problema. Es importante analizar la representaci\'on de los individuos 
y los m\'etodos de selecci\'on/reemplazo y reproducci\'on utilizados. Tambi\'en se mencionan los m\'etodos de corte implementados.

\subsection{Codificaci\'on de los Individuos}
Dado que el problema a resolver es obtener los pesos de una red neuronal multicapa, 
se representa cada individuo como un arreglo de n\'umeros de precisi\'on doble de punto flotante, que contiene 
los valores de la matrices de pesos de la red neuronal. De esta forma, cada individuo resulta en un 
arreglo de $N$ valores, donde $N$ es la cantidad de ``conexiones'' que tiene la red entre sus neuronas.

La cantidad de individuos en la poblaci\'on inicial es un par\'ametro configurable del algoritmo, 
que representa el tama\~no de la poblaci\'on. Es importante destacar 
que los individuos de la poblaci\'on inicial se generan al azar, limitando los valores del arreglo que los representa
al intervalo $\left[-1, 1\right]$.

\subsection{Funci\'on de fitness}
La funci\'on de aptitud que se utiliza es la inversa del error cuadr\'atico medio, $E$, de la salida de la red, 
es decir $\frac{1}{E}$. Como se ver\'a en la secci\'on II, el algoritmo gen\'etico tiende a mejorar el 
\textit{fitness} promedio de los individuos a medida que transcurren las generaciones. Esto implica que
$\frac{1}{E}$ crece, haciendo que $E$ disminuya, y por ende, se obtienen pesos
que hacen que la red de una salida con mejor precisi\'on.


\subsection{Selecci\'on}
El objetivo del m\'etodo de selecci\'on es tomar un subconjunto de los individuos m\'as aptos de la poblaci\'on
para el proceso de reproducci\'on. 
A continuaci\'on se listan los m\'etodos de selecci\'on utilizados en este trabajo.

\begin{itemize}
 \item Elite
 \item Roulette
 \item Universal
 \item Boltzmann
 \item Elite+Roulette
 \item Elite+Boltzmann
\end{itemize}



\subsection{Reproducci\'on}
La reproducci\'on es el proceso encargado de generar una determinada cantidad de descendientes a partir de un
subconjunto de individuos.
En \'este trabajo la reproducci\'on se realiza de a dos progenitores por vez, obteniendo
dos descendientes. Para la reproducci\'on se utilizan tres operadores gen\'eticos:

\begin{itemize}
 \item Cruce
 \item Mutaci\'on
 \item Backpropagation
\end{itemize}

Los tipos de cruce implementados en este trabajo son:

\begin{itemize}
 \item Cl\'asico
 \item M\'ultiple
 \item Uniforme Parametrizado
 \item Anular
\end{itemize}

Los m\'etodos de mutaci\'on utilizados en este trabajo son:

\begin{itemize}
 \item Cl\'asica
 \item No Uniforme
\end{itemize}

El operador Backpropagation consiste en entrenar con cierta probabilidad a los individuos resultantes 
del cruce y la mutaci\'on con el m\'etodo tradicional del
gradiente descendente una determinada cantidad de \'epocas. Para todas las pruebas se utiliz\'o
un entrenamiento de 50 \'epocas. Para la probabilidad se utilizaron distintos valores 
que se ver\'an a lo largo de \'este informe.

\subsection{Reemplazo}
El reemplazo se encarga de seleccionar, a trav\'es del m\'etodo especificado, los individuos m\'as 
aptos en el conjunto de los originarios de la poblaci\'on en esa generaci\'on y los obtenidos de la reproducci\'on. 
Es importante destacar que tanto al comienzo de la generaci\'on 
como luego del reemplazo, la cantidad de individuos es siempre igual, es decir que la 
cantidad de individuos no var\'ia entre generaciones. Los m\'etodos utilizados para el reemplazo 
son los mismos que los utilizados para la selecci\'on.

\subsection{M\'etodos de corte}
Para la ejecuci\'on del algoritmo gen\'etico se precisa un m\'etodo de corte, el cual expresa una condici\'on, 
tal que al cumplirse se da por finalizada la ejecuci\'on del algoritmo y se procede a analizar 
las caracter\'isticas de la poblaci\'on obtenida. Los m\'etodos de corte utilizados y sus par\'ametros son los siguientes:
\begin{itemize}
  \item M\'axima cantidad de generaciones:
  \begin{itemize}
    \item \textit{maxGeneration}: n\'umero m\'aximo de generaciones.
  \end{itemize}
  \item Contenido:
  \begin{itemize}
    \item \textit{iter}: cantidad de generaciones que transcurren entre cada comparaci\'on.
    \item \textit{tolContent}: tolerancia de la diferencia entre el \textit{fitness} del mejor individuo y el de \textit{iter} generaciones atr\'as.
  \end{itemize}
  \item Estructura:
  \begin{itemize}
    \item \textit{iter}: cantidad de generaciones que transcurren entre cada comparaci\'on.
    \item \textit{tolStructure}: tolerancia de la diferencia entre la desviaci\'on standard del valor de \textit{fitness} de la poblaci\'on actual y la de \textit{iter} generaciones atr\'as.
  \end{itemize}
  \item Entorno al \'optimo:
  \begin{itemize}
    \item \textit{tolOptimal}: Cota en la aptitud del individuo m\'as apto de la poblaci\'on.
  \end{itemize} 
\end{itemize}

La cantidad de generaciones que transcurren entre cada comparaci\'on siempre es 10.

\section{Resultados y Conclusiones}

Los indicadores que se analizan en todos los resultados son:
\begin{itemize}
\item El mejor \textit{fitness} alcanzado en la poblaci\'on, y por ende el individo que representa el menor $E$ como salida de la red.
\item El promedio del \textit{fitness} de toda la poblaci\'on en cada generaci\'on. Esto es indicador de qu\'e tan buenos son los pesos en una poblaci\'on.
\item Desv\'io standard del \textit{fitness} en una generaci\'on. Indicador de la diversidad de la poblaci\'on. Cuanto m\'as cercano a 0, menor es la diversidad.
\end{itemize}

En cada secci\'on se var\'ia una caracter\'istica del algoritmo, el resto de los par\'ametros se mantienen fijos.
Los par\'ametros default que se utilizan para todas las corridas salvo que se exprese lo contrario son:
\begin{itemize}
\item \textbf{Cantidad de individos:} 40
\item \textbf{Tama\~no de la matr\'iz de pesos:} 501
\item \textbf{Criterio de corte:} M\'aximo 50 generaciones
\item \textbf{Cruce:} Cl\'asico
\item \textbf{Mutaci\'on:} Cl\'asico
\item \textbf{Selecci\'on:} Elitte+Roulette
\item \textbf{Reemplazo:} Elitte+Roulette
\item \textbf{Probabilidad de cruce:} 0.8
\item \textbf{Probabilidad de mutaci\'on:} 0.001
\item \textbf{Probabilidad de entrenamiento:} 0.15
\item \textbf{Cantidad de \'epocas que se entrena:} 50
\end{itemize}


\subsection{Criterio de corte}
La variaci\'on del criterio no altera los resultados en cada generaci\'on, pero refleja cuando se ha llegado 
a un resultado aceptable, o bien transcurrido una cierta cantidad de generaciones. 
Estos criterios fueron usados \'unicamente para hacer pruebas y encontrar la mejor manera de 
que el algoritmo finalize cuando ya no evoluciona perceptiblemente. 
La mejor configuraci\'on encontrada para lograr esto es usar una estrategia de corte por estructura o contenido. 
Esto se debe a que la poblaci\'on deja de evolucionar cuando la diversidad desaparece o el mejor individuo 
no mejora luego de varias generaciones.\\ 

Estas variaciones no mejoran los resultados, solo ayudan detener el algoritmo cuando la diversidad disminuye
o ya no hay cambios significativos. Las estrategias de corte por generaciones y solucion \'optima 
no son las mejores ya que, al no conocer la respuesta del problema, los valores a considerar 
son arbitrarios y pueden finalizar la ejecuci\'on cuando el algoritmo a\'un est\'a progresando, 
o avanzar varias generaciones cuando este ya no evoluciona.

\subsection{Backpropagation}
La implementaci\'on que mejores resultados trajo fue la de entrenar con el operador gen\'etico de backpropagation
en cada generaci\'on, a cada individuo con una probabilidad determinada.

En la Figura \ref{def} se puede observar la salida del algoritmo gen\'etico con una probabilidad de entrenamiento 
de $0.15$. Esto es decir, que aproximadamente el $15\%$ de los hijos resultantes del cruce y mutaci\'on 
se entrenan en cada generaci\'on. Como se puede observar, a las 50 generaciones se llega a un \textit{fitness} 
de 80, aproximadamente un $E=0.0125$. Luego de 500 generaciones vemos que se llega a un promedio de $130$ de valor 
de aptitud, lo cual es un error cuadr\'atico medio menor a $0.008$.

En la Figura \ref{1} se observa la salida del algoritmo sin entrenamiento, es decir, con una probabilidad igual a $0$. 
Se ve que luego de 500 generaciones no se ha llegado a ning\'un resultado aceptable, alcanzando solamente un \textit{fitness} 
de 4, es decir $E=0.25$.

Si se aumenta la probabilidad de entrenamiento, se llega a mejores resultados en menor cantidad de generaciones. 
Por ejemplo con una probabilidad de entrenamiento de $0.3$, se alcanz\'o en promedio un \textit{fitness} de 100, $E=0.01$ 
(Figura \ref{3}). Como desventaja de aumentar la probabilidad de entrenamiento, 
a medida que la cantidad de individuos entrenados por generaci\'on aumenta, la ejecuci\'on 
se vuelve computacionalmente m\'as costosa.

\subsection{Mutaci\'on}
Se fue variando la probabilidad de mutaci\'on para observar distintos resultados. Se observa que 
cuanto mayor es la porci\'on de cada individuo que se muta, peores resultados se alcanzan. 
En las Figuras \ref{6}, \ref{7} y \ref{8}, se utiliz\'o probabilidad de mutaci\'on $p_m$ de 0.001, 0.0001 y 0 respectivamente, 
se observa que a medida que $p_m$ decrece, se obitnen mejores resultados.

Se hicieron pruebas sobre los distintos tipos de mutaci\'on, la cl\'asica y la no uniforme, 
pero no se obtuvieron resultados que difieran perceptiblemente.

\subsection{Selecci\'on y Reemplazo}

En esta secci\'on se obtuvieron varios resultados.

El primero que se puede apreciar es que al utilizar el m\'etodo de selecci\'on Elite, 
la diversidad decrece r\'apidamente. Esto se puede observar en la Figura \ref{17}, 
en donde se ve claramente como la diversidad tiende a $0$ en poca cantidad de generaciones. 

Lo segundo es que al utilizar un m\'etodo de selecci\'on que combina Elite con Roulette, 
se obtienen mejores resultados generalmente. En la Figura \ref{def} se puede observar 
la combinaci\'on de los m\'etodos, que a partir de las 150 generaciones se alcanza un \textit{fitness} de 120 aproximadamente, 
mientras que en las Figuras \ref{17} y \ref{13} no se llega a 90 en ninguna de las dos.

Usando el m\'etodo de selecci\'on Roulette se puede ver como el \textit{fitness} del mejor individuo tiende a oscilar. 
Esto se debe a que este m\'etodo no garantiza que los mejores individuos pasen a la siguiente generaci\'on,
simplemente tienen m\'as probabilidad de hacerlo. \'Este resultado era esperado. 

Por \'ultimo se puede notar que si se usa Elite o una combinaci\'on con Elite el mejor \textit{fitness} 
siempre mejora o en el peor de los casos se mantiene igual al de la generaci\'on anterior ya que Elite garantiza 
que los $N$ mejores individuos de una generaci\'on pasen a la siguiente (ver Figuras \ref{def}, \ref{17} y \ref{13})

\subsection{Cruce}
En la figura \ref{14} se puede observar el resultado del algoritmo gen\'etico para todos los tipos de cruce
implementados en este trabajo pr\'actico. Si bien a primera vista se puede ver notables diferencias, \'esto
no permite llegar a ninguna interpretaci\'on o conclusi\'on definitiva, ya que se ejecutaron multiples veces
las pruebas con cada tipo de cruce, y los resultados fueron siempre diferentes en cuanto a \textit{fitness} alcanzado
o diversidad de la poblaci\'on. Si se puede establecer que si bien el operador gen\'etico de cruce aporta
diversidad a la poblaci\'on para poder explorar globalmente el espacio de soluciones, no genera individuos
m\'as aptos como resultado del cruce.

\section*{Conclusiones finales}

Una conclusi\'on importante es que no se obtuvieron buenos resultados utilizando solamente algoritmos gen\'eticos. El $E$ de la salida de la red va bajando a medida que pasan las generaciones, pero no se llegan a resultados aceptables en comparaci\'on a los obtenidos del entrenamiento de la red neuronal.

En el m\'etodo de selecci\'on y reemplazo Elite, se concluye que la la diversidad decrece r\'apidamentey el \textit{fitness} 
se estanca, ya que el promedio de \textit{fitness} de todos los individuos es muy cercano al mejor \textit{fitness}
y por ende, todos los individuos son similares. Los mejores resultados se obtienen con combinaciones de 
Elite ya que se preservan los mejores individos de generaci\'on en generaci\'on sin perder la diversidad.

El m\'etodo de mutaci\'on, sin importar de qu\'e tipo sea, no d\'a buenos resultados, 
ya que en la mayor\'ia de los casos, el resultado de la mutaci\'on sobre un individuo genera otro con menor aptitud. 
Esto se debe a que la mutaci\'on hace cambios aleatorios a un arreglo de pesos. 
Estos cambios sin embargo, ayudan a mantener la diversidad de la poblaci\'on, sin la cual, la evoluci\'on del algoritmo 
se estancar\'ia.

Por \'ultimo pero no menos importante, se concluye que dado que los algoritmos gen\'eticos exploran el espacio de soluci\'on
globalmente con mayor diversidad, con menor costo computacional se alcanzan mejores resultados en cuanto al error
cuadr\'atico medio obtenido, frente al m\'etodo cl\'asico del grandiente descendente en el entrenamiento de la red.
Adem\'as, para funciones no derivables o con discontinuidades, el algoritmo del gradiente descendente no funcionaria, mientras
que con algoritmos gen\'eticos si puede resolverse.

\newpage
\onecolumn
\section*{Anexo}

\begin{figure}[ht]
	\begin{center}
		\includegraphics[width=0.75\textwidth] {../matlab/mfiles/default500gen/default500gen.png}
        \caption{Corte en 500 generaciones. 15\% de entrenamiento. M\'etodo de selecci\'on Elite+Roulette.}
			\label{def}
	\end{center}
\end{figure}

\begin{figure}[ht]
	\begin{center}
		\includegraphics[width=\textwidth] {../matlab/mfiles/sintrain500gen/sintrain500gen.png}
        \caption{Corte en 500 generaciones, sin entrenamiento.}
			\label{1}
	\end{center}
\end{figure}

\begin{figure}[ht]
	\begin{center}
		\includegraphics[width=0.75\textwidth] {../matlab/mfiles/3/maru.png}
        \caption{Corte en 50 generaciones, 30\% de entrenamiento.}
			\label{3}
	\end{center}
\end{figure}

\begin{figure}[ht]
	\begin{center}
		\includegraphics[width=0.75\textwidth] {../matlab/mfiles/6/tommy.png}
        \caption{Probabilidad de mutaci\'on de cada individo de 0.001.}
			\label{6}
	\end{center}
\end{figure}
\begin{figure}[ht]
	\begin{center}
		\includegraphics[width=0.75\textwidth] {../matlab/mfiles/7/tommy.png}
        \caption{Probabilidad de mutaci\'on de cada individo de 0.0001.}
			\label{7}
	\end{center}
\end{figure}
\begin{figure}[ht]
	\begin{center}
		\includegraphics[width=0.75\textwidth] {../matlab/mfiles/8/tommy.png}
        \caption{Sin mutaci\'on. Poca variaci\'on en la diversidad. Buenos resultados.}
			\label{8}
	\end{center}
\end{figure}

\begin{figure}[ht]
	\begin{center}
		\includegraphics[width=0.75\textwidth] {../matlab/mfiles/diversidadconelite/diversidad_con_elite.png}
        \caption{M\'etodo de selecci\'on Elite. Se pierde la diversidad. Se estanca la evoluci\'on.}
			\label{17}
	\end{center}
\end{figure}

\begin{figure}[ht]
	\begin{center}
		\includegraphics[width=0.75\textwidth] {../matlab/mfiles/roulette250gen/roulette250gen.png}
	\caption{M\'etodo de selecci\'on Roulette. Peores resultados que Elite+Roulette.}
			\label{13}
	\end{center}
\end{figure}

\begin{figure}[ht]
	\begin{center}
		\includegraphics[width=0.75\textwidth] {../matlab/mfiles/crossImg/tommy.png}
        \caption{Diferentes m\'etodos de cruce. De izquierda a derecha: Cruce cl\'asico, Cruce M\'ultiple, Cruce Uniforme, Cruce Anular}
			\label{14}
	\end{center}
\end{figure}

\end{document}